﻿using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using MPI;
using System.Collections;

namespace Dwarf.Managed
{


    /// <summary>
    /// Solve the Graph traversal problem.
    /// </summary>
    /// <remarks> 
    ///For the demonstration purposes of the project,
    ///we have chosen Depth first search algorithm
    /// </remarks>
    class Solver
    {
        /// <summary>
        /// True for master process.
        /// </summary>
        public bool isRootThread;

        /// <summary>
        /// Instance of Graph.
        /// </summary>
        public Graph graph;

        public Solver()
        {
            if (Communicator.world.Rank == Settings.ROOT_PROCESS)
            {
                isRootThread = true;
            }

        }

        /// <summary>
        /// Based method.
        /// </summary>
        public void Solve()
        {
            
            Stack<int> s;
            if(isRootThread)
            {   
                Queue<int> q = new Queue<int>();
                //Partition the tree for all processors
                Partition(q);
                //send the tasks
                for(int i = 1; i < Communicator.world.Size; i++)
                {   
                    Communicator.world.Send<int>(q.Dequeue(),i,0);
                }
                s = new Stack<int>(q);
            } 
            else
            {   
                s = new Stack<int>();
                //receive the task 
                int recv;
                Communicator.world.Receive<int>(Settings.ROOT_PROCESS, 0, out recv);
                s.Push(recv);
            }

            Communicator.world.Barrier();

            //Distribute the array of counts.
            Communicator.world.Broadcast(ref graph.visited, Settings.ROOT_PROCESS);

            //while stack not empty 
            while (s.Count != 0)
            {
                //take the first element
                int u = s.Peek();
                //for all edges of current vertex
                bool hasNoVisited = true;
                for (int j = 0; j < graph.edgesMatrix[u].Length; j++)
                {
                    int count = graph.getVisited(graph.edgesMatrix[u][j]);
                    if (count == 0)
                    {
                        //adding new vertex to work stack
                        hasNoVisited = false;
                        s.Push(graph.edgesMatrix[u][j]);
                        graph.setVisited(graph.edgesMatrix[u][j]);
                    }
                }
                if (hasNoVisited)
                {
                    s.Pop();
                }
            
            }
        }

        //Partition the tree for all processors
        public void Partition(Queue<int> q) 
        { 
            int headId = graph.getHeadId();
            graph.setVisited(headId);
            q.Enqueue(headId);
            while ((q.Count != 0) && (q.Count < Communicator.world.Size))
            {
                int u = q.Peek();
                for(int j = 0; j < graph.edgesMatrix[u].Length; j++)
                {
                    int count =  graph.getVisited(graph.edgesMatrix[u][j]);
                    if(count == 0) 
                    {   
                        //adding new vertex to work queue
                        q.Enqueue(graph.edgesMatrix[u][j]);
                        graph.setVisited(graph.edgesMatrix[u][j]);
                    }
                }
                q.Dequeue();
            }
        }

        public void GatherResults()
        {
            //collect the results on master
            if (!isRootThread)
            {
                Communicator.world.Send(graph.visited, Settings.ROOT_PROCESS, 0);
            }
            else
            {
                int[] recv = new int[graph.getLength()];
                for (int i = 1; i < Communicator.world.Size; i++)
                {
                    Communicator.world.Receive(i, 0, ref recv);
                    for (int j = 0; j < graph.getLength(); j++)
                    {
                        graph.visited[j] += recv[j];
                    }
                }
            }
        }
    }
}
